#include "RedBlackTree.hpp"
#include <stdlib.h>
#include <iostream>
#include <string.h>
/**
 * 红黑树的性质
 * 1. 根节点 是黑色
 * 2. 节点是红色or黑色
 * 3. 所有叶子都是黑色。（叶子是NIL节点）
 * 4. 每个红色节点的两个子节点都是黑色
 * 5. 从任一节点都每个叶子的所有路径都包含相同树木的黑色节点
 *
 *
 */

using namespace std;

int getTreeDeepth(TreeNode *treeNode);

TreeNode *buildNode(TreeNode *root, const char *data)
{
    TreeNode *newNode;
    newNode = (TreeNode *)malloc(sizeof(TreeNode));
    if (newNode == NULL)
    {
        cout << "没有足够的内存空间了" << endl;
        return NULL;
    }
    newNode->root = NULL;
    newNode->data = data;
    newNode->parent = NULL;
    newNode->left = NULL;
    newNode->right = NULL;
    if (root != NULL)
    {
        newNode->root = root;
        for (TreeNode *x = root;;)
        {
            if (strcmp(x->data, data) < 0)
            {
                if (x->right == NULL)
                {
                    x->right = newNode;
                    newNode->parent = x;
                    newNode->red = !newNode->parent->red;
                    break;
                }
                x = x->right;
            }
            else if (strcmp(x->data, data) == 0)
            {
                free(newNode);
                return x;
            }
            else
            {
                if (x->left == NULL)
                {
                    x->left = newNode;
                    newNode->parent = x;
                    newNode->red = !newNode->parent->red;
                    break;
                }
                x = x->left;
            }
        }
    }
    return newNode;
}

TreeNode *rotateLeft(TreeNode *root, TreeNode *p)
{
    TreeNode *r, *pp, *rl; 
    if (p != NULL && (r = p->right) != NULL)
    {
        printf("rotateLeft Node(%s)\n", p->data);
        if ((rl = p->right = r->left) != NULL)
            rl->parent = p;
        if ((pp = r->parent = p->parent) == NULL)
            (root = r)->red = false;
        else if (pp->left == p)
            pp->left = r;
        else
            pp->right = r;
        r->left = p;
        p->parent = r;
    }
    return root;
}

TreeNode *rotateRight(TreeNode *root, TreeNode *p)
{
    TreeNode *l, *pp, *lr;
    if (p != NULL && (l = p->left) != NULL)
    {
        printf("rotateRight Node(%s)\n", p->data);
        if ((lr = p->left = l->right) != NULL)
            lr->parent = p;
        if ((pp = l->parent = p->parent) == NULL)
            (root = l)->red = false;
        else if (pp->right == p)
            pp->right = l;
        else
            pp->left = l;
        l->right = p;
        p->parent = l;
    }
    return root;
}

/** 平衡插入*/
int balanceInsertion(TreeNode *root, TreeNode *x)
{
    x->red = true;
    for (TreeNode *xp, *xpp, *xppl, *xppr;;)
    {
        if ((xp = x->parent) == NULL)
        {
            // 当前节点x没有父节点，标记尾黑色，满足性质1
            x->red = false;
            return 1;
        }
        else if ((!xp->red || (xpp = xp->parent) == NULL))
        {
            return 1;
        }
        if (xp == (xppl = xpp->left))
        {
            if ((xppr = xpp->right) != NULL && xppr->red)
            {
                xppr->red = false;
                xp->red = false;
                xpp->red = true;
                x = xpp;
            }
            else
            {
                if (x == xp->right)
                {
                    root = rotateLeft(root, x = xp);
                    xpp = (x = xp->parent) == NULL ? NULL : xp->parent;
                }
                if (xp != NULL)
                {
                    xp->red - false;
                    if (xpp != NULL)
                    {
                        xpp->red = true;
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        else
        {
            if (x == xp->left)
            {
                root = rotateRight(root, x = xp);
                xpp = (xp = x->parent) == NULL ? NULL : xp->parent;
            }
            if (xp != NULL)
            {
                xp->red = false;
                if (xp != NULL)
                {
                    xpp->red = true;
                    root = rotateLeft(root, xpp);
                }
            }
        }
    }
}